Kodowanie teksu [cz. 1]...

Za zaliczenie musiałem napisać program, który by ilustrował kilka prosrych algorytmów kodowania tekstu oraz ich słabych stron:

1. Szyfry podstawieniowe monoalfabetyczne.

Polagają one na zamianę znaku teksu jawnego na odpowiedni znak kryptogramu, przyczym dla całej wiadomość stosuje się odwzorowanie [i]jeden do jednego[/i].

Przykładem tego szyfru może być tzw. szyfr Cezara. Polega on na przyporządkowaniu każdej literze alfabetu łacińskiego liczby(A=0, B=1...) i przesunięciu każdej liczby o k np. równe 3 (ma tu miejsce tzw. przewijanie - gdy konczy sie alfabet przesuwamy sie do jego poczatku). Zakres można oczywiście rozszerzyć o zbiór znaków ASCI lub jakiś inny skończony zbiór znaków n. Funkcja szyfrująca więc będzie wyrażana wzorem:
[b]F(a)=(a+k) mod n[/b]
Co w w cpp wyglada następująco:

   for (int i = 0; i <= strlen(napis) - 1; i++)
   napis[i]=(napis[i]+k) % 255;

Aby odkodować ten tekst należy odjąć wartość k.

Można tez stosować przekształcenia wyższego rzędu.
Hmm. W sumie przyznam się, że nie wiem gdzie mam umieścić algoytm sortowania ROT-13, wiele osób się sprzecza czy to algorytm podstawieniowy monoalfabetyczny czy nie. Moim zdaniem jest. Dlatego tutaj wklejam kod:

char* rot13(char* napis)
{
   for (unsigned int i = 0; i <= strlen(napis) - 1; i++)
   {
      if (napis[i] >= 'A' && napis[i] <= 'M')
         napis[i] = char (napis[i] + 13);
      else if (napis[i] >= 'N' && napis[i] <= 'Z')
         napis[i] = char (napis[i] - 13);
      if (napis[i] >= 'a' && napis[i] <= 'm')
         napis[i] = char (napis[i] + 13);
      else if (napis[i] >= 'n' && napis[i] <= 'z')
         napis[i] = char (napis[i] - 13);
   }
   return napis;
}

Algorytm kodowania, jest również algorytmem dekodowania.

Następnym szyfrem tego typu może być np. NOT'owanie (negowanie*). W tym sposobie mamy doczynienia z czystą matematyką. Negacja polega na tym, że jeżeli np. mamy liczbę zapisaną w systemie binarnym 1110001 to operacja negacji spowoduje odwrucenie bitów, czyli uzyskamy 0001110. Algorytm kodowania, jest również algorytmem dekodowania.

char* not(char* napis)
{
   for (unsigned int i = 0; i <= strlen(napis) - 1; i++)
      napis[i] = ~(napis[i]);
   return napis;
}

W niektórych szyfrach podstawieniowych monoalfabetycznych używano również niestandardowych alfabetów szyfrowych. Np. szyfr cmentarny, gdzie klucz utworzono za pomocą rusunków stosowanych w grze kółko i krzyrzyk.

Na koniec omawiania szyfrów monoalfabetycznych należy wspomnieć, że wiekszość z nich jest w prosty sposób łamana na podstawie analizy częstości występowania liter lub znaków (nawet przy ataku bez tekstu jawnego). Z tego powodu ich praktyczne znaczenie jest znikome.

2. Szyfry podstawieniowe wieloalfabetyczne.

Stosuje się w nich wieleodwzorowań jednego znaku tekstu jawnego na znaki kryptogramu, przyczym każde odwzorowanie jest jeden do jednego, podobnie jak w szyfrach monoalfabetycznych. Jak więc widzimy szyfry wieloalfabetyczne ukrywają częstotliwość występowania znaków przez użycie wielu podstawień. Większość szyfrów tej grupy to szyfry okresowe o okresie d znaków. Klasycznym przykładem jest szyfr powstały w XVI wieku [b]szyfr Vigenere'a[/b].

Szyfrowanie polega tu na podstawie dowolnie wybranego słowa kluczowego (hasla). Do numeru (np. ASCI) każdego kolejnego znaku tekstu jawnego dodajemy numer odpowiadającego mu znaku słowa kluczowego i uzyskujemy znak kryptogramu. Gdy słowo kluczowe się skończy bierzemy je od początku. Przykład funkcji dla znaków ASCI:
[b]Fx=(a+k[x]) mod 255[/b]
Przykład:

char* koduj(char* tekst, char* haslo)
{
   unsigned int j = 0;
   for(unsigned int i = 0; i <= strlen(tekst); i++)
   {
      tekst[i] = char(tekst[i] + haslo[j]);
      if (j < strlen(haslo) - 1) j++; else j = 0;
   }
   return tekst;
}

Dekodowanie:
[b]Fx=(a-k[x]) mod 255[/b]
Przykład:

char* koduj(char* tekst, char* haslo)
{
   unsigned int j = 0;
   for(unsigned int i = 0; i <= strlen(tekst); i++)
   {
      tekst[i] = char(tekst[i] - haslo[j]);
      if (j < strlen(haslo) - 1) j++; else j = 0;
   }
   return tekst;
}

Szczególną odmianą może tu być popularnie zwane XOR'owanie.
Na początek może wyjaśnie co to jest sama operacja xorowania. Jest tzw. dodawanie bez przeniesienia* tzn.:
np. jeżeli dodajemy liczbę 12(dec) czyli 1100(bin) i 15(dec) czyli 1111(bin) otrzymamy 0011(bin) czyli 3(dec). Jak to wygląda:
[quote]
1- powinna wyjść z przeniesienia, ale pomijamy ją
1100
xor 1111
--------
0011
[/quote]
Najpierw dodajemy pisemnie obydwie liczby (system dwójkowy). Czyli 0+1=1, 0+1=0, 1+1=0(jedynka na przenisienie), 1+1=0, co po przeliczeniu daje 3(dec).
Wzór jest podobny jak powyżej:

char* xoruj(char* tekst, char* haslo)
{
   unsigned int j = 0;
   for(unsigned int i = 0; i <= dlugosc; i++)
   {
      tekst[i] = char(tekst[i] ^ haslo[j]);
      if (j < strlen(haslo) - 1) j++; else j = 0;
   }
   return tekst;
}

Okresowe szyfry wieloalfabetyczne również nie należą do najbezpieczniejszych. Po wyznaczeniu okresu takiego szyfru jest on bezproblemowo łamany. Do wyznaczaniu okresu szyfru służa dwie metody: wskaźnika zgoność i Kasiskiego.

I to już będzie koniec, niestety.
Wkrótce zapraszam na dalszą część.

• Dla przyszłych studentów informatyki (Politechniki Koszalińskiej). Ostrzegam, że na pierwszym roku będzie trzeba znać nie tylko xorowanie, negacje itd. będzie trzeba jeszcze skutecznie umieć posługiwać się różnym kodowaniem liczb, niestety nie tylko będzie bin, hex, dec, oct, tylko takie brzydactwa jak kody ud, kd, kod Grey'a. I w nich jeszcze będzie trzeba wykonywać wszystkie działania.